package com.atguigu.sort;

import java.util.Arrays;

public class HeapSort2 {

    // 兄弟们，千万不要被索引值和数值给整懵了，就只是一个形式而已，你只要记住父节点的左右孩子的表达式即可 2 * i + 1 和 2 * i + 2

    public static void main(String[] args) {
        // 要求将数组进行升序排序
        int[] arr = {4,6,8,5,9} ;
        heapSort(arr);
        /*
        // 创建80000个的随机的数组
        int[] arr = new int[8000000] ;
        for(int i = 0 ; i < 8000000 ; i++){
            arr[i] = (int) (Math.random() * 80000000);  // 生成一个[0,8000000)的数，为什么要取怎么大，为了避免取到相同的值
        }
//        Date date1 = new Date() ;   // 实体类
//        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//        String date1Str = sdf.format(date1);
//        System.out.println("排序前的时间是=" + date1Str);

        long before = System.currentTimeMillis() ;
        //System.out.println("排序前的时间是=" + System.currentTimeMillis()) ;

        heapSort(arr);

//        Date date2 = new Date() ;   // 实体类
//        String date2Str = sdf.format(date2);
//        System.out.println("排序后的时间是=" + date2Str);  // 选择排序用时4s
        long after = System.currentTimeMillis() ;

        System.out.println("执行总时间" + (after - before) / 1000.0 + "s");    // 80000数据，执行总时间0.014s
                                                                              // 800000数据，执行总时间0.213s
                                                                             // 8000000数据，执行总时间2.496s

         */

    }


    // 编写一个堆排序的方法
    public static void heapSort(int[] arr){
        int temp = 0 ;  // 用来交换首尾元素的临时变量
        System.out.println("堆排序！！");

        // 分步完成
//        adjustHeap(arr, 1, arr.length);
//        System.out.println("第一次" + Arrays.toString(arr));   // 4,9,8,5,6

//        为什么此时不会将表示对多少个元素的调整，length - 1？？
        // 因为第一次调整，并没有找到一个真正最大的数，故调整的数组元素还是length
//        adjustHeap(arr, 0, arr.length);
//        System.out.println("第二次" + Arrays.toString(arr));   // 9,6,8,5,4

        // 完成我们的最终代码
        // 1）将待排序序列构造成一个大顶堆,根据升序降序需求选择大顶堆或小顶堆
        // 叶子节点是从根节点开始计数，然后从上到下，从左向右计数，故 arr.length / 2 - 1 求出来的是最后一个非叶子节点的【索引值】

        // arr.length / 2 - 1 求出来的是最后一个非叶子节点的【索引值】，从右向左，从下向上进行遍历调整
        // "从下向上"和"从右向左"都是完全二叉树而言，不懂可以自己根据要排序的数组，脑补一个完全二叉树
        // 但切记：在每一个非叶子节点处判断时，其左子节点和右子节点要从左向右查看
        // 综上：这里并没有递归入栈，而是每次执行完一个adjustHeap()后，返回到调用点，然后再次进行遍历，并没有涉及到递归
        // 当第一次for循环执行完毕之后，会产生一个大堆顶，然后执行第二个for循环

        // 此for循环是确定非叶子节点的左子节点,切记：完全二叉树，如果是最后一个非叶子节点，那么一定会存在左子节点，不一定存在右子节点
        // 故下面需要对右子节点进行判断，k + 1 < length，避免越界
        // 其实：这里的k也可以看做是一个指针【指示器】

        // 综上：此for循环是确定第一个大顶堆，
        // 步骤是：从最后一个非叶子节点开始进行搜索，求取每一个局部的大顶堆
        for(int i = arr.length / 2 - 1 ; i >= 0 ; i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr, i,i, arr.length); // 注意：每一趟局部堆顶，都会选出一个当前排序的局部最大堆顶
        }


        /**
         * 关于上下两个for循环调用adjustHeap()方法的区别  【明确一点：这里其实是有用到递归的，每次递归后元素个数少一，】
         * 上面调用adjustHeap()方法，目的是生成第一个大顶堆而我们获取大顶堆需要从最后一个非叶子节点进行搜索，此时得到第一个最大值，然后下面的for循环将第一个和最后一个元素交换，只会将其 最大值元素分隔开，下一次不用考虑
         * 而下面的for循环调用adjustHeap()方法是为了得到最大值的堆顶元素，因为此时刚好从第一次获取到大顶堆的元素时候，除了第一个元素和最后一个元素进行交换，
         * 【其他元素的相对位置】没有变化，故第二次获取大顶堆速度会变得很快，因为 此时我们传入的参数是adjustHeap(arr, 0, j);即把第一个位置的元素的index=0传入，此时，当前的堆顶元素，
         * 虽然不是最大值，但其和左右子节点元素进行比较，得到此时的最大值，并不一定是最终大堆顶的最大值
         * 若此时若还有左子节点，此时需要再次循环，下一次判断是否下一次节点是局部调整的最大值，若是，则就直接break；否则又要调整；以此类推
         *  然后将当前序列和最后一个元素和大堆顶的堆顶元素进行交换。之后以此类推。
         *
         * 综上：第一次获取大堆顶需要局部调整多次，直到i=0，此时得到大堆顶。
         * 第2,3.。。n次之后，此时需先将之前的堆顶元素和其相邻的左右子节点进行比较，
         * 然后若左子节点任然存在左子节点[i=k条件 结合 k = k * 2 + 1 之后的k值不操作当前]将将较大的元素放到堆顶处，局部调整一次，
         * 此时还需要看看是否有左子节点，以及是否在 有左子节点的时候后 ，此时的节点不是局部的大堆顶，若满足，则又要进行交换，得到最后的大堆顶。
         *
         * 老师独家讲解：
         *      但是 你要明确一点的是，刚开始我们是为了效率比较好，所以才会先处理最后一个非叶子节点，如果是真实调整的话，是从根节点开始进行调整
         *      并且：你要记得其实第一次获取到的大堆顶后，其相对的位置关系大体已经确定，故，此时直接从堆顶元素出发，可能只需要调整一次即可得到最大元素【理想情况】
         *          如果不理想的话，也是正常的，此时调整的次数就不止一次。【原因在于有不确定的因素：是否在 有左子节点的时候后 ，此时的节点是否是局部的大堆顶】
         */

        /**
         * 1）将待排序序列构造成一个大顶堆,根据升序降序需求选择大顶堆或小顶堆
         * 2) 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端
         * 3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，
         *     反复执行调整+交换步骤，直到整个序列有序。
         *
         * 你有没有发现，反复执行是不是，相当于递归，重复相同的操作。【但这里没有实际意义上的递归入口和出口】
         * 我们这里其实将其认作是递归主要是因为看到在一个for循环内部调用的是同一个方法，其实当你在debug过程中，你会发现
         * adjustHeap()方法在每个调用点，只会开辟一个栈【作为调用的方法区域栈】，然后在这个栈中，利用for循环来进行向底部搜索判断，
         * 并没有一直压栈，只是 k = k * 2 + 1 会让人以为是向下层搜索【导致的压栈】
         *
         * 这里规定一点：这里的顶部是说，从二叉树的每个非叶子节点来看，那么都是可以看做是"顶部"
         * 【还有一种理解思路：你千万不要看成是 （每个非叶子节点来看，那么都是可以看做是"顶部"），但在完全二叉树来看是在底部，这样你会误认为是“递推”】
         * 其实不然，这里这并不是递推，因为递推是需要从叶子节点底部出发，而这里是从每一个待遍历的非叶子节点的顶部出发，向叶子节点方向判断局部堆顶
         *
         * 即我们下面的for循环首先是将第一次顶部的大堆顶的元素和末尾元素交换。
         * 那这是不是和分治算法有点关联？？？。
         * 这里声明一点，分治算法是要有最小问题解【递归出口】，而这里并没有体现。
         *
         * 综上：堆排序的大顶堆方法：其实是使用了类似汉诺塔的 递归思想【但无具体实现】，而且有分治算法的模式，即三步骤。【但无具体体现最小子问题】
         *
         */
        // 第二个for循环是不断的交换和重构，此时除了第一次排序生成的第一个大堆顶是在第一个for循环形成的，
        // 其他剩下的每一趟生成的大堆顶都是在第二个for循环内部实现的，并没有再执行第一个for循环代码
        // 临界条件：若之前j=2，即还剩下两个元素 执行adjustHeap(arr, 0, j)，之后j-- 得到j=1，故此时arr[j]=arr[1],其还需和arr[0]进行交换元素，
        // 之后进入adjustHeap(arr, 0, j);方法，因为此时只剩下一个元素，j=1，故就直接不符合条件，跳出循环，
        // 即最后这一次也需要进入，因为前面变量j定义的方式，如果退出的条件改为j > 1,则会造成若第一个位置和第二个位置的元素arr[0]，arr[1]是逆序的，则此时无法进行交换
        // 综上：此处for循环的j：代表要交换元素【当前要调整元素的最后一个元素】的下标
        for(int j = arr.length - 1 ; j > 0 ; j--){  // 一共有arr.length = 5 个元素，故我们只需调整【即交换元素】大堆顶四次
            // 交换
            // 每一次交换都是和堆顶元素交换，即arr[0],下标为0的堆顶元素
            temp = arr[j] ;
            arr[j] = arr[0] ;
            arr[0] = temp ;
            // 上面已经将第一个大顶堆排序好了，此时移动到末尾，然后就需要重复此步骤再排 "次大顶堆"，
            // 而这里有个比较高效的算法，就是此时并没有又将 begin 指向 倒数第二个位置，可能第一次排序，已经差不多排序成功了，
            // 只是差了一点，那么排第二个顶堆的时候，其实可以省省力，直接从最高的顶堆出发，如果运气好的话，可能速度还更快。
            adjustHeap(arr, 0,0, j);  // why？？？   综上：此处的j：代表要调整元素的个数
            // 故虽然两处是同一个变量j，但表示的意思不同
        }

        System.out.println("数组=" + Arrays.toString(arr));


    }

    // 将一个数组（脑补为一个完全二叉树，此 完全二叉树 按照数组的顺序存储），然后将其调整成一个大顶堆

    /**
     * 功能：完成 将 以 i 对应的非叶子节点的树调整为大顶堆
     * 举例：int[] arr = {4,6,8,5,9}; => i = 1 => adjustHeap => 得到{4,9,8,5,6}
     * 如果我们再次调用adjustHeap  传入的是 i = 0 => 得到{4,9,8,5,6} => {9,6,8,5,4}
     * @param arr   待调整的数组
     * @param begin     表示非叶子节点在数组中的索引  【注意：begin=0代表是数组的第一个元素，也是二叉树的第一个节点】
     * @param end       表示追踪到后面要被覆盖的位置，即刚好可以存放下最刚开始保存的temp元素，且符合局部大堆顶
     * @param length    表示对多少个元素的调整，length 是在逐渐减少
     *
     *  我一直以为每一次调用adjustHeap()方法都会生成一个大顶堆，并不是，第一次调用会生成，当前非叶子节点的堆顶（局部调整）
     *  此时还需要进行从右向左，从下向上，然后生成每一次的堆顶，当最后i=0时候，此时调整好次序时，此时的堆顶即为大堆顶。此时才刚刚找到了一个最大值，
     *  将其和最后一个位置的元素交换位置，这才是第一次大顶堆的调整【里面涉及到多个局部堆顶的调整】，下一次将最后一个位置的最大元素不作为下一趟进行
     *  调整大堆顶的元素，故此时 arr.length-1
     *
     *
     *  没想到，这里使用的覆盖的思想，之前有进行研究。就是被覆盖的元素如果有需要的话，要提前保存，
     *         而这里存在传递“覆盖”的思想，即本质上还是 “覆盖”的思维，套路一个样。
     *
     *  int end = begin ;   // end指针是追踪最后需要覆盖的位置，其刚好可以存放下 最刚开始保存的temp元素，且符合局部大顶堆
     *                      // 切记：最好不要和最刚开始的begin弄混淆了
     *
     *  此方法的实际作用是：确定局部堆顶的最大
     */
    public static void adjustHeap(int[] arr,int begin ,int end,int length){


        // 这里貌似存在一个坑，如果要对当前非叶子节点，且其左子节点是非叶子节点，那么就需要进行判断了
        // 所以，要判断的指标始终是 索引值为i下的元素 arr[i]，这个是永恒不变的，你千万不要在 k = 2 * k + 1 步长下，就转换了判断的指标
        int temp  = arr[begin] ;    // 先取出当前元素的值，保存在临时变量；因为当前位置可能会被覆盖，所以要提前保存
        // 开始调整
        // 说明
        // 1. k = begin * 2 + 1  => k 是 i节点的左子节点
        // 2. length ：代表调整当前堆的时候的元素个数，不包括已调整好的，同时 k < length : 是为了防止k下标越界
        // 3. for循环最后的一个k的增量：k = k * 2 + 1是为了处理可能当前叶子节点的左子树还存在左子节点【是不是感觉有点像深度优先dfs，即摆放当前层【非叶子节点】的局部堆顶】
        for(int k = begin * 2 + 1 ; k < length ; k = k * 2 + 1){

            // k + 1 < length：添加这一句是为了加快检索的效率【优点：如果不存在右子节点，指针k就直接和左子节点比较】，【等价为】同时捎带也对左子树的右子节点进行判断
            // k + 1 看起来是不是进行特殊判断，即去除不必要的检索条件【提前考虑】
            if(k + 1 < length && arr[k] < arr[k + 1]){    // 说明左子节点的值小于右子节点的值
                k++ ;   // 当符合上面的if条件后， k 指向右子节点
            }

            if(arr[k] > temp){  // 如果子节点大于父节点
                // 把较大的值，赋给当前
                arr[end] = arr[k] ;   // 将子节点的值移动到前面父节点处，而父节点的原始值由temp保存

                // 下面这种情况可能是在什么情况下出现 ???
                // 如果之前已经局部对非叶子节点进行大顶堆的局部排序，但是在经过几趟排序后，
                // 此之前的非叶子节点恰好又是当前节点的左子节点，那么此时就要考虑如果当前节点的元素值比之前的非叶子节点的元素值小，
                // 那么在交换后，如果之前排序好的局部大堆顶造成影响后，之前非叶子节点的元素值比其左右子节点小，则此时还需要再次向
                // 其左子节点进行大顶堆排序，即相当于这一趟排序，其实是多排序了之前排序过的堆顶，【把之前的那个影响了】；

                // 而如果之前的非叶子节点恰好又是当前节点的左子节点，但此时当前节点的元素值比之前的非叶子节点的元素值小大
                // 此时在这趟堆顶排序时候，就可以直接跳过下面这个本不该移动的代码判断，即直接执行下面的break语句
                end = k ;  // ！！！ i 指向 k，继续循环比较，把 i看做是一个指针，可能当前叶子节点的左子树还存在左子节点，
                //  // 所以需要对原来的非叶子节点的索引值i 进行 覆盖
            }else{  //arr[k] <= temp
                break ;     // 难点！！！这里为什么可直接break；【无论该节点是否存在子节点，满足arr[k] <= temp条件，都可以跳出循环】
                // 但实际上最根本的原因是arr[k] <= temp，且非叶子节点是按照从右向左，从下向上的顺序查找【子节点是按照从左向右查找】
                // 故如果这个条件满足，则说明此排序没有要进行交换元素，而之前的排序好的也不用动了。故就可以直接跳出循环

                // 因为我们进行堆顶局部排序时候，是遵循，从右向左，从下到上的方向进行局部堆顶排序。
                // 故下面的顺序，如果arr[k]没有变化位置，说明还是可以按照之前的顺序排列，故就不用比较了
                // 如果变化位置，那就是上面arr[k] > temp的情况，此时
            }
        }
        // 当for循环结束后，我们己经将以i 为父节点的树的最大值，放在了 排序当前非叶子节点的堆顶（局部调整）
        // 上面这个注释貌似有点小问题：存在小疑惑

        // 这里存在一点小疑惑：就是这里的end其实并不是我们传递进来要判断的位置的begin的位置，【你可以看看 上面存在 end = k】
        // 这不就说明end指针移动了，所以准确来讲end指针指向的位置是 可以被覆盖的位置，其刚好可以存放下 最刚开始保存的temp元素，且符合局部大顶堆

        // 如果在 k = k * 2 + 1的情况下，刚好其左右子节点都小于 temp，那么就说明当前的i位置就是可以被 temp 元素 覆盖的位置【符合大顶堆】
        arr[end] = temp ; // 将temp值放到调整后的位置，即当前位置的元素值是局部的大堆顶

        // 我感觉，为了避免疑惑，可以再定义一个变量来取代i，不然你会以为：就是当for循环结束后，我们己经将以i 为父节点的树的最大值，放在了 排序当前非叶子节点的堆顶（局部调整）
        // 刚好，在这个版本下，我又定义了一个变量end来表示追踪到 后面要被覆盖的位置，刚好此时不会弄混淆了
    }
}